This paper shows that a quantum mechanical algorithm that can queryinformation relating to multiple items of the database, can search a databasein a single query (a query is defined as any question to the database to whichthe database has to return a (YES/NO) answer). A classical algorithm will belimited to the information theoretic bound of at least O(log N) queries (whichit would achieve by using a binary search).
展开▼